package com.offer;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * @program: leetcode
 * @author: jzhou
 * @date: 2022-12-04 16:28
 * @version: 1.0
 * @description: 用两个栈实现队列
 **/
public class CQueue {
//    Stack<Integer> in ;
//    Stack<Integer> out ;
//    public CQueue() {
//        in = new Stack<>();
//        out = new Stack<>();
//    }

    /**
     * ArrayDeque是采用数组方式实现的双端队列。
     * ArrayDeque的出队入队是通过头尾指针循环，利用数组实现的。
     * ArrayDeque容量不足时是会扩容的，每次扩容容量增加一倍。
     * ArrayDeque可以直接作为栈使用。当用作栈时，性能优于Stack，当用于队列时，性能优于LinkedList。
     * 无容量大小限制，容量按需增长。
     * 非线程安全队列，无同步策略，不支持多线程安全访问。
     */
    Deque<Integer> in;
    Deque<Integer> out;

    public CQueue() {
        in = new ArrayDeque<Integer>();
        out = new ArrayDeque<Integer>();
    }

    public void appendTail(int value) {
        in.push(value);
    }

    public int deleteHead() {
        if (in.isEmpty() && out.isEmpty()) return -1;
        if (!out.isEmpty()) return out.pop();
        moveData();
        return out.pop();
    }

    private void moveData() {
        while (!in.isEmpty()){
            out.push(in.pop());
        }
    }

    public static void main(String[] args) {
        CQueue queue = new CQueue();
        queue.appendTail(1);
        queue.appendTail(2);
        queue.appendTail(3);
        queue.appendTail(4);
        System.out.println(queue.deleteHead());
        System.out.println(queue.deleteHead());
        queue.appendTail(5);
        queue.appendTail(6);
        System.out.println(queue.deleteHead());
        System.out.println(queue.deleteHead());
        System.out.println(queue.deleteHead());
        System.out.println(queue.deleteHead());
    }
}
